#include <vector>
class Solution {
    int m, n;
    vector<vector<int>> dp;
public:
    void DpBuilder(string& s1, string& s2) {
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s1[i-1] == s2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
    }
    string LCSBuilder(vector<vector<int>>& dp, string& s1, string& s2, int i, int j) {
        if (i == 0 || j == 0) return "";
        if (s1[i-1] == s2[j-1]) {
            return LCSBuilder(dp, s1, s2, i-1, j-1) + s1[i-1];
        } else if (dp[i-1][j] >= dp[i][j-1]) {
            return LCSBuilder(dp, s1, s2, i-1, j);
        } else {
            return LCSBuilder(dp, s1, s2, i, j-1);
        }
    }
    string LCS(string& s1, string& s2) {
        m = s1.size(), n = s2.size();
        if(m == 0 || n == 0) return "-1";
        dp = vector<vector<int>>(m+1, vector<int>(n+1, 0));
        DpBuilder(s1, s2);
        if (dp[m][n] == 0) return "-1";
        return LCSBuilder(dp, s1, s2, m, n);
    }
};